package com.ryujung.dp.leetCode_5;

/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/description/
 *
 * algorithms
 * Medium (29.47%)
 * Likes:    2070
 * Dislikes: 0
 * Total Accepted:    244.4K
 * Total Submissions: 828.3K
 * Testcase Example:  '"babad"'
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * 
 * 示例 1：
 * 
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 
 * 
 * 示例 2：
 * 
 * 输入: "cbbd"
 * 输出: "bb"
 * 
 * 
 */

// @lc code=start
class Solution2 {
    /**
     * 中心扩散法：
     * 1. 回文字串的中心是单个字符
     * 1. 回文字串的中心是两个字符
     * Time:   O(n^2)
     * Space:  O(1)
     */
    public String longestPalindrome(String s) {
        int l = s.length();
        if (l < 2) {
            return s;
        }

        String maxPal = "";

        for (int i = 0; i < l - 1; i++) {
            //当前字符为单个字符的回文中心时的最大回文字串
            String oddMaxPal = centrelMaxPal(s, i, i);

            //当前字符为两个字符的回文中心时的最大回文字串
            String evenMaxPal = centrelMaxPal(s, i, i + 1);

            maxPal = maxPal.length() < oddMaxPal.length() ? oddMaxPal : maxPal;
            maxPal = maxPal.length() < evenMaxPal.length() ? evenMaxPal : maxPal;
        }
        return maxPal;
    }

    /**
     * 中心扩散算法的辅助方法，
     * 寻找text字符串中，以center1和center2为中心的最长回文字串
     */
    public String centrelMaxPal(String text, int left, int right) {
        String maxPal = text.substring(left, right);

        //charAt范围：[0,text.length-1]    substring范围：[0,text.length]
        while (text.charAt(left) == text.charAt(right)) {
            //如果center1或者center2到达边界
            if (left == 0 || right == text.length() - 1) {
                return text.substring(left, right + 1);
            }
            //可以继续扩散
            left--;
            right++;
        }

        return text.substring(left + 1, right);
    }

    /**
     * 动态规划方式:
     * dp[i][j]表示s的子串[I,J]是否为回文串
     * Time:  O(n^2)
     * Space: O(n^2)
     * 测试耗时： 119ms
     */
    public String longestPalindrome1(String s) {
        int l = s.length();

        boolean[][] dp = new boolean[l][l];

        String maxPal = "";
        for (int i = l - 1; i >= 0; i--) {
            for (int j = i; j < l; j++) {
                //i和j的字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    //同一个或相邻字符
                    if (i == j || Math.abs(j - i) == 1) {
                        dp[i][j] = true;

                        //相同的两个字符是不相邻的
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    //当dp[i][j]为true时，判断当前的i和j对应的字串是否大于已有的maxPal
                    //如果大于则进行替换，否则继续循环
                    if (j - i + 1 > maxPal.length() && dp[i][j]) {
                        maxPal = s.substring(i, j + 1);
                    }
                }
            }
        }
        return maxPal;
    }

    /**
     * 暴力匹配方式
     * Time:  O(n^3)
     * Space: O(n^2)
     * 测试耗时： 1522ms 效率低
     */
    public String longestPalindrome2(String s) {
        int maxLen = 1;
        String res = "";

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length() + 1; j++) {
                int seqLen = j - i + 1;
                String subSeq = s.substring(i, j);
                if (seqLen > maxLen && isPalindrome(subSeq)) {
                    maxLen = seqLen;
                    res = subSeq;
                }
            }
        }
        return res;
    }

    /**
     * 判断是否为回文字符串，暴力匹配的辅助函数
     */
    public boolean isPalindrome(String s) {
        if (s.isEmpty())
            return false;

        int l = s.length();
        int end = l - 1;
        int start = 0;
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        String str = "cbbd";
        // String str = "googleeel";

        System.out.println(s.longestPalindrome(str));
    }
}
// @lc code=end
